import functools


class Solution:
    def findIntegers(self, num: int) -> int:
        # print(bin(num))

        bit = num.bit_length()

        ans = 0
        last = 0

        for i in range(bit - 1, -1, -1):
            val = (1 << i)
            if num & val:  # 当前首位数字为1
                num -= val
                ans += self.dfs(i, 0)
                if last == 1:
                    break
                last = 1
            else:  # 当前首位数字为0
                last = 0

            # 处理最后1位的情况
            if i == 0:
                ans += 1
            # print(i, ":", last, "->", ans)

        return ans

    @functools.lru_cache(None)
    def dfs(self, bit: int, last: int = 0):
        """计算整位的不含连续1的非负整数"""
        if bit == 0:
            return 1
        if last == 0:
            return self.dfs(bit - 1, 0) + self.dfs(bit - 1, 1)
        else:  # last == 1
            return self.dfs(bit - 1, 0)


if __name__ == "__main__":
    print(Solution().findIntegers(5))  # 5

    # 自制用例
    print(Solution().findIntegers(3))  # 3
    print(Solution().findIntegers(4))  # 4
    print(Solution().findIntegers(8))  # 6
    print(Solution().findIntegers(16))  # 9
